package pers.whj.util.tree;

public class SplayTreeImpl<T extends Comparable<T>> extends BinarySearchTreeImpl<T> implements SplayTree<T> {
    public SplayTreeImpl() {
    }

    @Override
    public void splay(T data) {
        this.root = splay(this.root, data);
    }

    @Override
    public boolean insert(T data) {
        if (super.insert(data)) {
            this.root = splay(this.root, data);
            return true;
        }
        return false;
    }

    protected Node<T> splay(Node<T> node, T data) {
        if (node == null || data == null) {
            return node;
        }
        Node<T> newNode = new Node<>(null);
        Node<T> l = newNode;
        Node<T> r = newNode;
        Node<T> tmp;
        while (true) {
            int compare = data.compareTo(node.data);
            if (compare < 0) {
                if (node.left == null) {
                    break;
                }
                // rotate right
                if (data.compareTo(node.left.data) < 0) {
                    tmp = node.left;
                    node.left = tmp.right;
                    tmp.right = node;
                    node = tmp;
                    if (node.left == null) {
                        break;
                    }
                }
                r.left = node;
                r = node;
                node = node.left;
            } else if (compare > 0) {
                if (node.right == null) {
                    break;
                }
                // rotate left
                if (data.compareTo(node.right.data) > 0) {
                    tmp = node.right;
                    node.right = tmp.left;
                    tmp.left = node;
                    node = tmp;
                    if (node.right == null) {
                        break;
                    }
                }
                l.right = node;
                l = node;
                node = node.right;
            } else {
                break;
            }
        }
        l.right = node.left;
        r.left = node.right;
        node.left = newNode.right;
        node.right = newNode.left;
        return node;
    }

    @Override
    protected boolean remove(T data, Node<T> node, Node<T> parent) {
        if (search(node, data) == null) {
            return false;
        }
        boolean isLeftChild = parent != null && parent.left == node;
        node = splay(node, data);
        Node<T> x;
        if (node.left != null) {
            // let the precursor of node to be the root node
            x = splay(node.left, data);
            // remove this node
            x.right = node.right;
        } else {
            x = node.right;
        }
        node.reset();
        if (parent == null) {
            this.root = x;
        } else {
            if (isLeftChild) {
                parent.left = x;
            } else {
                parent.right = x;
            }
        }
        this.size--;
        return true;
    }
}